#include <stdio.h>
#include <stdlib.h>
#define maxsize 80
typedef struct BNode
{
    BNode *lchild;
    BNode *rchild;
    int data;
} BNode, *BTree;

struct Queue
{
    BNode *node[maxsize];
    int front;
    int rear;
};

// 获取第K层的结点个数
int getLayerNum(BTree T, int k)
{
    // 初始化队列
    Queue q;
    q.front = q.rear = 0;

    // 根节点入队
    q.node[q.rear] = T;
    q.rear = (q.rear + 1) % maxsize;

    int level = 1;
    while (q.front != q.rear)
    {
        int num = (q.rear - q.front + maxsize) % maxsize;
        if (level == k)
        {
            return num;
        }
        for (int i = 0; i < num; i++)
        {
            // 队首节点出队
            BNode *tmp = q.node[q.front];
            q.front = (q.front + 1) % maxsize;

            // 出队结点左右孩子入队
            if (tmp->lchild)
            {
                q.node[q.rear] = tmp->lchild;
                q.rear = (q.rear + 1) % maxsize;
            }
            if (tmp->rchild)
            {
                q.node[q.rear] = tmp->rchild;
                q.rear = (q.rear + 1) % maxsize;
            }
        }
        level++;
    }
    return 0;
}

// 求第k层结点个数
int printLayer(BTree T,int k)
{
    if (T == NULL)
        return 0;
    // 初始化队列
    Queue q;
    q.rear = q.front = 0;

    // 根结点入队
    q.node[q.rear] = T;
    q.rear = (q.rear + 1) % maxsize;
    int layer = 0;
    while (q.front != q.rear)
    {
        layer++;
        int len = (q.rear - q.front + maxsize) % maxsize;
        if(layer == k)
            return len;
        for (int i = 0; i < len; i++)
        {
            // 出队
            BNode *tmp = q.node[q.front];
            q.front = (q.front + 1) % maxsize;

            // 左右孩子入队
            if (tmp->lchild != NULL)
            {
                q.node[q.rear] = tmp->lchild;
                q.rear = (q.rear + 1) % maxsize;
            }

            if (tmp->rchild != NULL)
            {
                q.node[q.rear] = tmp->rchild;
                q.rear = (q.rear + 1) % maxsize;
            }
        }
    }
    return 0;
}

// 队满条件： (q.rear + 1) % maxsize == q.front
// 队空条件： q.rear == q.front
// 队长：(q.rear - q.front + maxsize) % maxsize
void printLayer2(BTree T)
{
    // 初始化队列
    Queue q;
    q.front = q.rear = 0;

    // 根结点入队
    q.node[q.rear] = T;
    q.rear = (q.rear + 1) % maxsize;

    while (q.front != q.rear)
    {
        // 记录队列长度，表示该层结点个数
        int num = (q.rear - q.front + maxsize) % maxsize;
        for (int i = 0; i < num; i++)
        {
            // 队首节点出队
            BNode *tmp = q.node[q.front];
            q.front = (q.front + 1) % maxsize;

            // 访问出队结点
            printf("%d ", tmp->data);

            // 出队结点的左右孩子入队
            if (tmp->lchild)
            {
                q.node[q.rear] = tmp->lchild;
                q.rear = (q.rear + 1) % maxsize;
            }
            if (tmp->rchild)
            {
                q.node[q.rear] = tmp->rchild;
                q.rear = (q.rear + 1) % maxsize;
            }
        }
        printf("\n");
    }
}

BNode *GetNode(int x)
{
    BNode *node = (BNode *)malloc(sizeof(BNode));
    node->data = x;
    node->lchild = NULL;
    node->rchild = NULL;
}

/***
 *          1
 *      3       2
 *   4        6    5
 * */
int main()
{
    BTree T = GetNode(1);
    T->lchild = GetNode(3);
    T->rchild = GetNode(2);
    T->lchild->lchild = GetNode(4);
    T->rchild->rchild = GetNode(5);
    T->rchild->lchild = GetNode(6);
    printLayer2(T);

    int num = getLayerNum(T, 100000);
    printf("%d ", num);

    return 0;
}